package no24;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/5/17 13:06
 * II 反转链表
 * https://leetcode.cn/problems/UHnkqh/
 */
public class Solution2 {

    // 方法一: 三指针思路
    public ListNode reverseList01(ListNode head) {
        // 如果链表为空, 或者只有1个节点, 直接返回 head
        if (head == null || head.next == null) {
            return head;
        }
        // 三指针反转链表
        ListNode left = head;
        ListNode mid = left.next;
        ListNode right = mid.next;
        // 逐个节点反转
        while (right != null) {
            mid.next = left;
            left = mid;
            mid = right;
            right = right.next;
        }
        // 反转最后一个节点和第一个节点
        mid.next = left;
        head.next = null;
        // 返回 mid, 即反转链表后的头节点
        return mid;
    }

    // 方法二: 头插法思路
    public ListNode reverseList02(ListNode head) {
        // 如果链表为空, 或者只有1个节点, 直接返回 head
        if (head == null || head.next == null) {
            return head;
        }
        // 头插法的思路(不带头节点的方式)
        ListNode newHead = null;
        while (head != null) {
            // 每次逐个将 head 节点从原链表删除, 拼接到新链表上
            ListNode newNode = head;
            head = head.next;
            newNode.next = newHead;
            newHead = newNode;
        }
        return newHead;
    }


    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
